package leetcode_400;

/**
 *@author 周杨
 *CountingBits_338 给定一个数字N 返回其1-n整数中bit 1的个数
 *describe:采用动态规划的思想 每次设立哨兵 AC 100%
 *2018年7月6日 上午10:27:37
 */
public class CountingBits_338 {

	public static void main(String[] args) {
		CountingBits_338 test=new CountingBits_338();
		int res[]=test.countBits(2);

	}
	public int[] countBits(int num) {
	     int [] res=new int[num+1];
	     for(int i=1;i<=num;) {
	    	 res[i]=1;
	    	 i*=2;
	     }
	     int next=2;
	     for(int i=3;i<=num;++i) {
	    	 if(res[i]==1) {
	    		 next=i;
	    		 continue;
	    	 }
	    	 res[i]=1+res[i-next];
	     }
	     return res;
	}
}
